/**
 * 作者:TC
 * 时间:大整数乘法 15:38
 * 描述:没有bug
 */
import java.util.Scanner;
public class MultiplicationLargeIntegers {
  //理想状态下
    public long DivideSameConquer(long x,long y,int n)
    {
        long result;
        if(x==0||y==0)
        {
            return 0;
        }else if(n==1){
            result = (long)( x * y);
            return result;
        }else{
           long a1=x/(long)Math.pow(10,n/2);//计算a1
           long a0=x-a1*(long)Math.pow(10,n/2);
           long b1=y/(long)Math.pow(10,n/2);
           long b0=y-b1*(long)Math.pow(10,n/2);
           long a1_b1=DivideSameConquer(a1,b1,n/2);//递归计算c0=a1*b1
           long a0_b0=DivideSameConquer(a0,b0,n/2);//递归计算c2=a0*b0
           long a1_b1_a0_b0=DivideSameConquer(a0+a1,b0+b1,n/2)-a1_b1-a0_b0;//递归计算c1
            //利用公式c=c0*10^n+c1*10^(n/2)+c2 c1=(a1+a0)*(b1+b0)-a1*a0-b1*b0
           result=a1_b1*(long)Math.pow(10,n)+a1_b1_a0_b0*(long)Math.pow(10,n/2)+a0*b0;
           return result;
        }
    }
    //不理想状态下时位数为奇数且不相同时
    public long DivideUnSameConquer(long x,long y,int n,int m){
        long result;
        if(x==0||y==0){
          return 0;
      }else if((n==1&&m==1)||n==1||m==1){
      return x*y;
      }else{
    int n1=n/2,m1=m/2;
    int n0=n-n1,m0=m-m1;
    long a1=(long)(x/(long)Math.pow(10,n1));
    long a0=(long)(x%(long)Math.pow(10,n1));
    long b1=(long)(y/(long)Math.pow(10,m1));
    long b0=(long)(y%(long)Math.pow(10,m1));
    long a1_b1=DivideUnSameConquer(a1,b1,n1,m1);
    long a0_b0=DivideUnSameConquer(a0,b0,n0,m0);
    //在不理想状态下是利用推导公式x*y=2a1_b1*10^n1+m1+(a1*10^n1-a0)*(B0-b1*10^m1)+2b0_b1
    long a1_b1_a0_b0=DivideUnSameConquer((long)a1*(long)Math.pow(10,n1)-a0, b0-(long)b1*(long)Math.pow(10,m1), n1, m1);
    result= (long)(2 * a1_b1 * Math.pow(10, (n1 + m1)) + a1_b1_a0_b0 + 2 * a0_b0);
          return result;
     }
    }
    public static void main(String[] args) {
        Scanner SC=new Scanner(System.in);
        long result;
        System.out.println("请输入大整数a：");
        long a=SC.nextLong();
        System.out.println("请输入大整数b：");
        long b=SC.nextLong();
        long x,y;
        x=a;
        y=b;
        int n1=1,m=1;
        while(a/10!=0)//计算n
        {
            n1++;
            a/=10;
        }
        while(b/10!=0) {
            m++;
            b /= 10;
        }
        int  n=m>n1?m:n1;//计算两位整数的最大位数
        System.out.println("两位数的最大位数n="+n);
        MultiplicationLargeIntegers multi=new MultiplicationLargeIntegers();
        if(m==n&&m%2==0) {
             result = multi.DivideSameConquer(x, y, n);
            System.out.println("理想状态下：a*b通过大整数乘法的结果为："+result);
        }else{
            result=multi.DivideUnSameConquer(x,y,n1,m);
            System.out.println("不理想状态下：a*b通过大整数乘法的结果为："+result);
        }

    }
}
